// 队列
class ArrayDeque {
    constructor() {

        // 当前数组大小
        let _size = 0;
        Object.defineProperty(this, 'size', {
            get() {
                return _size;
            },
            set() {
                throw new Error('无法修改size属性')
            },
            configurable: false,
        })

        let font = 0;

        // 初始化数组
        let _store = new Array();
        /**
         * 入队列，没有最大容量
         * 时间复杂度:O(1)
         * @param ele
         */
        this.push = function (ele) {
            _store[_size] = ele;
            _size++;
        }
        /**
         * 出队列
         * 时间复杂度:O(n)
         */
        this.pop = function () {
            if (_size <= 0) {
                throw new Error("超出队列范围");
            }
            let ele = _store[0];
            //  移动元素
            for (let i = 1; i < _size; i++) {
                _store[i - 1] = _store[i];
            }
            _size--;
            return ele;
        }
        /**
         * 访问队首元素
         * 时间复杂度:O(1)
         */
        this.peek = function () {
            if (_size <= 0) {
                throw new Error("超出队列范围");
            }
            let ele = _store[0];
            return ele;
        }
        /**
         * 转换为数组
         * 时间复杂度:O(n)
         */
        this.toArray = function () {
            let newStore = new Array(this.size);
            for (let i = 0; i < newStore.length; i++) {
                newStore[i] = _store[i];
            }
            return newStore
        }
    }
    /**
     * 元素的大小
     * 时间复杂度:O(1)
     */
    size() {
        return this.size;
    }
}

/**
固定容量大小的队列
**/
class FixArrayDeque {
    constructor(initCapacity) {

        Object.defineProperty(this, 'capacity', {
            get() {
                return initCapacity;
            },
            set() {
                throw new Error('无法修改initCapacity属性')
            },
            configurable: false,
        })

        // 当前数组大小
        let _size = 0;
        Object.defineProperty(this, 'size', {
            get() {
                return _size;
            },
            set() {
                throw new Error('无法修改size属性')
            },
            configurable: false,
        })

        let font = 0;

        // 初始化数组
        let _store = new Array(initCapacity);
        /**
         * 入队列
         * 时间复杂度:O(1)
         * @param ele
         */
        this.push = function (ele) {
            if (_size >= initCapacity ) {
                throw new Error("超出队列范围");
            }
            let position = (font+_size) % initCapacity;
            _store[position] = ele;
            _size++;
        }
        /**
         * 出队列
         * 时间复杂度:O(1)
         * @param ele
         */
        this.pop = function () {
            if (_size <= 0) {
                throw new Error("超出队列范围");
            }
            _size--;
            let ele = _store[font];
            font++;
            font = font % initCapacity;
            return ele;
        }
        /**
         * 访问队首元素
         * 时间复杂度:O(1)
         */
        this.peek = function () {
            if (_size <= 0) {
                throw new Error("超出队列范围");
            }
            let ele = _store[font];
            return ele;
        }
        /**
         * 转换为数组
         * 时间复杂度:O(n)
         */
        this.toArray = function () {
            let newStore = new Array(this.size);
            for (let i = 0; i < this.size; i++) {
                newStore[i] = _store[(font+i)%this.capacity];
            }
            return newStore
        }
    }
    /**
     * 元素的大小
     * 时间复杂度:O(1)
     */
    size() {
        return this.size;
    }
}

/**
 * 链接节点
 */
class LinkedNode {
    constructor(val, next) {
        this.val = val;
        this.next = next;
    }
}

class LinkedDeque {
    constructor() {
        // 当前数组大小
        let _size = 0;
        Object.defineProperty(this, 'size', {
            get() {
                return _size;
            },
            set() {
                throw new Error('无法修改size属性')
            },
            configurable: false,
        })

        let _headNode = null;
        let _tailNode = null;

        /**
         * 入队列
         * 时间复杂度:O(1)
         * @param ele
         */
        this.push = function (ele) {
            if (_headNode == null) {
                _headNode = new LinkedNode(ele, null);
                _tailNode = _headNode;
            } else {
                _tailNode.next = new LinkedNode(ele, null);
                _tailNode = _tailNode.next;
            }
            _size++;
        }
        /**
         * 出队列
         * 时间复杂度:O(1)
         */
        this.pop = function () {
            if (_headNode == null) {
                throw new Error("超出队列范围");
            }
            let val = _headNode.val;
            if (_headNode == _tailNode) {
                _tailNode = null;
                _headNode = null
            } else {
                _headNode = _headNode.next;
            }
            _size--;
            return val;
        }
        /**
         * 访问队首元素
         * 时间复杂度:O(1)
         */
        this.peek = function () {
            if (_headNode == null) {
                throw new Error("超出队列范围");
            }
            let val = _headNode.val;
            return val;
        }
        /**
         * 转换为数组
         * 时间复杂度:O(n)
         */
        this.toArray = function () {
            let newStore = new Array(this.size);
            let current = _headNode;
            let index = 0;
            while (current != null) {
                newStore[index] = current.val;
                current = current.next;
                index++;
            }
            return newStore
        }
    }

    /**
     * 元素的大小
     * 时间复杂度:O(1)
     */
    size() {
        return this.size;
    }
}

class DoubleLinkedNode {
    constructor(val, next, prev) {
        this.val = val;
        this.next = next;
        this.prev = prev;
    }
}

class DoubleLinkedQueue {

    constructor() {

        // 当前数组大小
        let _size = 0;
        Object.defineProperty(this, 'size', {
            get() {
                return _size;
            },
            set() {
                throw new Error('无法修改size属性')
            },
            configurable: false,
        })

        let _headNode = null;
        let _tailNode = null;

        /**
         * 将元素添加到队首
         * 时间复杂度：O(1)
         * @param ele
         */
        this.pushFirst = function (ele) {
            _size++;
            if (_headNode == null) {
                _headNode = new DoubleLinkedNode(ele, null, null);
                _tailNode = _headNode;
            } else {
                let tmp = new DoubleLinkedNode(ele, _headNode, null);
                _headNode.prev = tmp;
                _headNode = tmp;
            }
        }
        /**
         * 将元素添加到队尾
         * 时间复杂度：O(1)
         * @param ele
         */
        this.pushLast = function (ele) {
            _size++;
            if (_tailNode == null) {
                _tailNode = new DoubleLinkedNode(ele, null, null);
                _headNode = _tailNode;
            } else {
                let tmp = new DoubleLinkedNode(ele, null, _tailNode);
                _tailNode.next = tmp;
                _tailNode = tmp;
            }
        }

        /**
         * 访问队首元素
         * 时间复杂度：O(1)
         */
        this.popFirst = function () {
            if (_headNode == null) {
                throw new Error("超出队列范围");
            }
            _size--;
            let result = _headNode.val;
            let tmp = _headNode;
            _headNode = _headNode.next;
            if (_headNode != null) {
                _headNode.prev = null;
            } else {
                _tailNode = null;
            }
            tmp.next = null;
            return result;
        }
        /**
         * 访问队尾元素
         * 时间复杂度：O(1)
         */
        this.popLast = function () {
            if (_tailNode == null) {
                throw new Error("超出队列范围");
            }
            _size--;
            let result = _tailNode.val;
            let tmp = _tailNode;
            _tailNode = _tailNode.prev
            if (_tailNode != null) {
                _tailNode.next = null;
            } else {
                _headNode = null;
            }
            tmp.prev = null;
            return result;
        }

        /**
         * 访问队首元素
         * 时间复杂度：O(1)
         */
        this.peekFirst = function () {
            if (_headNode == null) {
                throw new Error("超出队列范围");
            }
            return _headNode.val;
        }
        /**
         * 访问队尾元素
         * 时间复杂度：O(1)
         */
        this.peekLast = function () {
            if (_tailNode == null) {
                throw new Error("超出队列范围");
            }
            return _tailNode.val;
        }

        /**
         * 转换为数组
         * 时间复杂度:O(n)
         */
        this.toArray = function () {
            let newStore = new Array(this.size);
            let current = _headNode;
            let index = 0;
            while (current != null) {
                newStore[index] = current.val;
                current = current.next;
                index++;
            }
            return newStore
        }
    }

    /**
     * 元素的大小
     * 时间复杂度:O(1)
     */
    size() {
        return this.size;
    }
}

class DoubleArrayQueue {
    constructor(initCapacity) {
        if(typeof initCapacity === "undefined"){
            throw new Error('请设置initCapacity属性')
        }
        
        Object.defineProperty(this, 'capacity', {
            get() {
                return initCapacity;
            },
            set() {
                throw new Error('无法修改initCapacity属性')
            },
            configurable: false,
        })

        // 当前数组大小
        let _size = 0;
        Object.defineProperty(this, 'size', {
            get() {
                return _size;
            },
            set() {
                throw new Error('无法修改size属性')
            },
            configurable: false,
        })

        let _font = 0;

        // 初始化数组
        let _store = new Array(initCapacity);

        /**
         * 将元素添加到队首
         * 时间复杂度：O(1)
         * @param ele
         */
        this.pushFirst = function (ele) {
            if (_size + 1 > initCapacity) {
                throw new Error('超出队列范围')
            }
            _font = (_font + initCapacity - 1) % initCapacity;
            _store[_font] = ele;
            _size++;
        }
        /**
         * 将元素添加到队尾
         * 时间复杂度：O(1)
         * @param ele
         */
        this.pushLast = function (ele) {
            if (_size + 1 > initCapacity) {
                throw new Error('超出队列范围')
            }
            let setIndex = (_font + _size) % initCapacity;
            _store[setIndex] = ele;
            _size++;
            return ele;
        }

        /**
         * 访问队首元素
         * 时间复杂度：O(1)
         * @param ele
         */
        this.popFirst = function () {
            if (_size - 1 < 0) {
                throw new Error('超出队列范围')
            }
            _size--;
            let result = _store[_font];
            _font = (_font + 1) % initCapacity;
            return result;
        }
        /**
         * 访问队尾元素
         * 时间复杂度：O(1)
         * @param ele
         */
        this.popLast = function () {
            if (_size - 1 < 0) {
                throw new Error('超出队列范围')
            }
            let setIndex = (_font + _size-1) % initCapacity;
            _size--;
            return _store[setIndex];
        }

        /**
         * 访问队首元素
         * 时间复杂度：O(1)
         * @param ele
         */
        this.peekFirst = function () {
            if (_size <= 0) {
                throw new Error("超出队列范围");
            }
            return _store[_font];
        }
        /**
         * 访问队尾元素
         * 时间复杂度：O(1)
         * @param ele
         */
        this.peekLast = function () {
            if (_size <= 0) {
                throw new Error("超出队列范围");
            }
            let setIndex = (_font + _size-1) % initCapacity;
            let ele = _store[setIndex] ;
            return ele;
        }
        /**
         * 转换为数组
         * 时间复杂度:O(n)
         */
        this.toArray = function () {
            let newStore = new Array(this.size);
            for (let i = 0; i < this.size; i++) {
                newStore[i] = _store[(_font+i)%this.capacity];
            }
            return newStore
        }
    }

    /**
     * 元素的大小
     * 时间复杂度:O(1)
     */
    size() {
        return this.size;
    }
}